/*
 * @lc app=leetcode.cn id=862 lang=cpp
 *
 * [862] 和至少为 K 的最短子数组
 *
 * https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/description/
 *
 * algorithms
 * Hard (22.09%)
 * Likes:    534
 * Dislikes: 0
 * Total Accepted:    34.1K
 * Total Submissions: 141.6K
 * Testcase Example:  '[1]\n1'
 *
 * 给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组
 * ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。
 *
 * 子数组 是数组中 连续 的一部分。
 *
 *
 *
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：nums = [1], k = 1
 * 输出：1
 *
 *
 * 示例 2：
 *
 *
 * 输入：nums = [1,2], k = 4
 * 输出：-1
 *
 *
 * 示例 3：
 *
 *
 * 输入：nums = [2,-1,2], k = 3
 * 输出：3
 *
 *
 *
 *
 * 提示：
 *
 *
 * 1 <= nums.length <= 10^5
 * -10^5 <= nums[i] <= 10^5
 * 1 <= k <= 10^9
 *
 *
 */

// @lc code=start
#include <deque>
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int shortestSubarray(vector<int> &nums, int k) {
        int n = nums.size();
        int ans = n + 1;
        // 构建前缀和
        vector<long> pre_sum;
        pre_sum.push_back(0);
        for (auto num : nums) {
            pre_sum.push_back(pre_sum.back() + num);
        }
        deque<int> q;
        for (int i = 0; i <= n; ++i) {
            long cur_sum = pre_sum[i];
            while (!q.empty() && cur_sum - pre_sum[q.front()] >= k) {
                ans = min(ans, i - q.front());
                q.pop_front();
            }
            while (!q.empty() && pre_sum[q.back()] >= cur_sum) {
                q.pop_back();
            }
            q.push_back(i);
        }
        return ans < n + 1 ? ans : -1;
    }
};
// @lc code=end
